package leetcode.D100.T84;

import util.ListUtil;

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] left = new int[heights.length], right = new int[heights.length];
        int maxArea = 0;
        tranverse(left, heights, 0, heights.length-1, 1, -1);
        tranverse(right, heights, heights.length-1, 0, -1, heights.length);
        for (int i=0; i<heights.length; ++i) {
            int leftBorder = left[i] + 1, rightBorder = right[i] - 1;
            maxArea = Math.max(maxArea, (rightBorder - leftBorder + 1) * heights[i]);
        }
        return maxArea;
    }

    private void tranverse(int[] result, int[] heights, int start, int end, int step, int border) {
        Deque<Integer> dq = new LinkedList<>();
        while (start != end + step) {
            while (!dq.isEmpty() && heights[dq.getLast()] >= heights[start])
                dq.removeLast();
            result[start] = dq.isEmpty() ? border : dq.getLast();
            dq.addLast(start);
            start += step;
        }
    }
}
